/**
 * 给定M，如果某个数i，存在x，满足
 * i的x次方 % M = 1
 * 称为i是好的，问[2, M]之间好的数有多少个
 * 如果i和M互质，则 i的phi(M)次方 % M = 1
 * 所以就是问M一下互质的数量，即欧拉函数
 */
#include <bits/stdc++.h>
using namespace std;

struct Sieve{ // 线性筛法

using llt = int;
vector<bool> isComp; // isComp[i]表示i是否为合数
vector<llt> primes; // primes[i]是第i个质数
vector<llt> Euler;  // Euler[i]表示i的欧拉函数

Sieve(int SZ = 35000){
    primes.reserve(SZ);
    isComp.assign(SZ, false);    

    Euler.assign(SZ, 0);
    Euler[1] = 1;
    
    long long tmp;
    for(int i=2;i<SZ;++i){
        if(!isComp[i]){
            primes.push_back(i);
            Euler[i] = i - 1;
        }

        for(int j=0,n=primes.size();j<n&&(tmp=i*(long long)primes[j])<SZ;++j){
            isComp[tmp] = true;

            if(0 == i % primes[j]){
                Euler[tmp] = Euler[i] * primes[j];
                break;
            }else{
                Euler[tmp] = Euler[i] * (primes[j] - 1);
            }
        }
    }
}

}Sie(1000010);

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);

    int nofkase = 1; 
    cin >> nofkase;
    while(nofkase--){
        int m; cin >> m;
        cout << Sie.Euler[m] - 1 << endl;
    }
    return 0;
}